﻿#define _CRT_SECURE_NO_WARNINGS 1

#include "seqlist.h"
//顺序表

//1.线性表 

//线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
//用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
//线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
//线性表在物理上存储时，通常以数组和链式结构的形式存储。


//2.顺序表 

//2.1概念及结构
//顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
//储。在数组上完成数据的增删查改。

//顺序表一般可以分为：
//1. 静态顺序表：使用定长数组存储元素。

#define N 10000
typedef int SLDataType;

//静态顺序表---开少了浪费，开多了不够用
struct SeqList
{
	SLDataType arr[N];
	size_t size;
};

//2. 动态顺序表：使用动态开辟的数组存储。

//动态顺序表---按需申请
struct SeqList
{
	SLDataType* array;//动态开辟的数组
	size_t size;//有效数据的个数
	int capacity;//空间的容量
};



//2.2 接口实现 

//静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空
//间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间
//大小，所以下面我们实现动态顺序表

typedef struct SeqList
{
	SLDataType* array;//动态开辟的数组
	size_t size;//有效数据的个数
	int capacity;//空间的容量
}SL;

//对这个动态顺序表进行处理
//增删查改
//初始化：
void SeqInit(SL* ps)
{
	assert(ps != NULL);
	ps->array = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
	if (ps->array == NULL)
	{
		perror("SeqInit::malloc");
		return 0;
	}
	ps->capacity = INIT_CAPACITY;
	ps->size = 0;
}
// 检查空间，如果满了，进行增容
void CheckCapacity(SL* ps)
{
	assert(ps != NULL);
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->array, sizeof(SLDataType)*ps->capacity * 2);
		if (tmp==NULL)
		{
			perror("CheckCapacity::realloc");
			return;
		}
		ps->array = tmp;
		ps->capacity = ps->capacity * 2;
	}
}
// 顺序表尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
	assert(ps != NULL);
	//检查是否需要扩容，进行扩容
	CheckCapacity(ps);
	ps->array[ps->size] = x;
	ps->size++;
}//尾插的时间复杂度是 O（N）
// 顺序表尾删
void SeqListPopBack(SL* ps)
{
	assert(ps != NULL);
	//不能使用free来直接释放，因为在堆上申请数组释放的时候是一起释放，不能只释放一块
	//如果ps->size为0了就不要在popback了
	if (ps->size == 0)
		return;
	//也可以这样检查：assert(ps->size > 0);
	ps->array[ps->size - 1] = 0;
	ps->size--;
}//尾删的时间复杂度是 O（N）
// 顺序表头插
void SeqListPushFront(SL* ps, SLDataType x)
{
	assert(ps != NULL);
	int end = ps->size - 1;
	while (end>=0)
	{
		//检查是否需要扩容：
		CheckCapacity(ps);

		ps->array[end + 1] = ps->array[end];
		end--;
	}
	ps->array[0] = x;
	ps->size++;
}//头插n个数据的时间复杂度是O（N²）
// 顺序表头删
void SeqListPopFront(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size > 0);
	//从前往后挪
	int begin = 1;
	while (begin < ps->size)
	{
		ps->array[begin - 1] = ps->array[begin];
		begin++;
	}
	ps->size--;
}//头删n个数据的时间复杂度是O（N²）
// 顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps != NULL);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->array[i] == x)
		{
			return i;
		}
	}
	return -1;
}
// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDataType x)
{
	assert(ps != NULL);
	assert(pos >= 0 && pos <= ps->size);
	//检查是否需要扩容：
	CheckCapacity(ps);
	//pos前面插入：
	int end = ps->size - 1;
	while (pos <= end)
	{
		ps->array[end + 1] = ps->array[end];
		end--;
	}
	ps->array[pos] = x;
	ps->size++;
}
// 顺序表删除pos位置的值
void SeqListErase(SL* ps, size_t pos)
{
	assert(ps != NULL);
	assert(pos >= 0 && pos < ps->size);

	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->array[begin - 1] = ps->array[begin];
		begin++;
	}
	ps->size--;


}
// 顺序表销毁
void SeqListDestory(SL* ps)
{
	free(ps->array);
	ps->array = NULL;
	ps->capacity = ps->size = 0;
}
// 顺序表打印
void SeqListPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->array[i]);
	}
	printf("\n");
}


//2.3 顺序表的问题及思考 
//问题：
//1. 中间 / 头部的插入删除，时间复杂度为O(N)
//2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗
//3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到
//200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间


//2.3 数组相关面试题 
//1. 原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。
//题目：
//给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素
//元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

//思路：用两个指针进行完成，一个指针往后遍历，只要该数不是val，那么两个指针都往后移动
//如果这个数是val，一个指针向后移动，找到不是Val的数，然后赋值给另一个指针，如此循环

//1.双指针
int removeElement(int* nums, int numsSize, int val) 
{
	int* src = nums;
	int* dst = nums;
	int count = 0;
	for (int i = 0; i < numsSize; i++)
	{
		if (*src != val)
		{
			*dst = *src;
			dst++;
			src++;
			count++;
		}
		else
		{
			src++;
		}
	}
	return count;
}

//2.使用下标
int removeElement(int* nums, int numsSize, int val)
{
	int src = 0;
	int dst = 0;
	while (src < numsSize)
	{
		if (nums[src]!=val)
		{
			nums[dst] = nums[src];
			dst++;
			src++;
		}
		else
		{
			src++;
		}
	}
	return dst;
}



//2. 删除排序数组中的重复项，要求时间复杂度为O(N)，空间复杂度为O(1)。
//题目：
//给你一个 非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次 
//返回删除后数组的新长度。元素的 相对顺序应该保持一致 。然后返回nums中唯一元素的个数。
//更改数组 nums ，使nums的前 k 个元素包含唯一元素，并按照它们最初在 nums中出现的顺序排列
//nums的其余元素与nums的大小不重要

//思路：用两个下标来完成，一个下标走在最前面，如果两个下标的数字相同，那么就继续往后遍历
//如果不相同，那么这个位置的数等于零一个下标下一个位置的数字

int removeDuplicates(int* nums, int numsSize) 
{
	int src = 0;
	int dst = 0;
	while (src < numsSize)
	{
		if(nums[src]==nums[dst])
		{
			src++;
		}
		else
		{
			nums[++dst] = nums[src];
		}
	}
	return dst + 1;
}


//3. 合并两个有序数组，要求时间复杂度为O(N)
//题目：
//给你两个按非递减顺序排列的整数数组nums1和nums2，另有两个整数m和n分别表示nums1和nums2中的元素数目。
//请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。
//注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中
//为了应对这种情况，nums1的初始长度为m + n，其中前m个元素表示应合并的元素，
//后n个元素为0 应忽略，nums2 的长度为n

//思路：第一个数组后面应该留有num2元素个数的空位置，然后从num1的最后开始往前进行两个数组比较
//依次放两个数组的最大值在num后面
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
	int end1 = m - 1;
	int end2 = n - 1;
	int dst = m + n - 1;
	while (end1 >= 0 && end2 >= 0)
	{
		if (nums1[end1] > nums2[end2])
		{
			nums1[dst--] = nums1[end1--];
		}
		else
		{
			nums1[dst--] = nums2[end2--];
		}
	}
	while (end2 >= 0)
	{
		nums1[dst--] = nums2[end2--];
	}
}





